package ch04.string_sort;

//低位优先的字符串排序
public class LSD {
    //待排序的数组
    static String[] a;
    static String[] aux;
    //a[i]的位数
    static int W;
    public static void init() {
        W = 7;
        a = new String[8];
        aux = new String[8];
        a[0] = "4PGC938";
        a[1] = "2IYE230";
        a[2] = "3CIO720";
        a[3] = "1ICK750";
        a[4] = "3CIO720";
        a[5] = "1OHV845";
        a[6] = "2RLA629";
        a[7] = "3ATW723";

    }


    public static void sort() {
        int N = a.length;
        int R = 256;

        for (int i = W - 1; i >= 0; i--) {
            int[] count = new int[R + 1];
            //计算频率
            //count[a[j].charAt(i)+1]记录前面的元素个数，也是下一个索引排序的起始位置
            for (int j = 0; j < N; j++) {
                count[a[j].charAt(i)+1]++;
            }
            //计算排在该元素前面的个数
            for (int j = 0; j < R; j++) {
                count[j + 1] += count[j];
            }
            //排序
            for (int j = 0; j < N; j++) {
                aux[count[a[j].charAt(i)]++] = a[j];
            }

            for (int j = 0; j < N; j++) {
                a[j] = aux[j];
            }


        }
    }

   /* public static void sort() {
        int n = a.length;
        int R = 256;   // extend ASCII alphabet size
        String[] aux = new String[n];

        for (int d = W-1; d >= 0; d--) {
            // sort by key-indexed counting on dth character

            // compute frequency counts
            int[] count = new int[R+1];
            for (int i = 0; i < n; i++)
                count[a[i].charAt(d) + 1]++;

            // compute cumulates
            for (int r = 0; r < R; r++)
                count[r+1] += count[r];

            // move data
            for (int i = 0; i < n; i++)
                aux[count[a[i].charAt(d)]++] = a[i];

            // copy back
            for (int i = 0; i < n; i++)
                a[i] = aux[i];
        }
    }*/

    public static void print(){
        for (String s : a) {
            System.out.println(s);
        }
    }

    public static void main(String[] args) {
        init();
        sort();
        print();
    }
}
